1. Field of the Invention
The present invention relates to method for wiring a semiconductor integrated circuit and a printed circuit board or the like, and especially relates to a wiring method utilizing a computer.
2. Description of the Prior Art
Owing to a recent development of miniaturization technology, the number of transistors to be embedded on a single chip in a large scale integration (LSI) circuit is ever increasing. There appears at present an LSI having more than a million of transistors on the single chip. On the other hand, a time necessary for developing a product needs to be short, and there is widely used a semi-custom LSI such as a gate array and standard cell. In the course of designing these LSI's, a computer-aided design (CAD) is indispensable.
As for a layout design as a physical stage for designing a circuit, a research and development therefor has been very active and there are available some typical technologies that have been in practical use for developing a product. There have been suggested many algorithms for automatic wiring methods. Among such algorithms, typical methods are a maze algorithm, a hierarchical algorithm, a line search algorithm and a channel router algorithm.
Among above algorithms, a Lee's maze algorithm (C. Y. Lee, "An Algorithm for Path Connections and Its Applications," IRE Transactions on Electronic Computers, Vol EC-10, pp 348-365, 1961) is the oldest one, and a variety of methods which are modified to speed up the Lee's maze algorithm have been conventionally used. It is partly because the Lee's maze algorithm is superior in a searching capability such that if there exists a solution there must be found a wiring route therefor and the solution can be obtained as a shortest routing.
However, it takes an enormous amount of time to process the maze algorithm, and when the maze algorithm is adopted for designing an LSI chip region it takes a few days to several weeks to complete a processing. Moreover, in the maze algorithm the processing is carried out net by net. Therefore, depending on selecting an processing order of a particular net, there may be a case where it becomes impossible to carry on wiring. Accordingly, the maze algorithm may be not suitable since an overall wiring can not be completed if the wiring order is not properly determined in advance.
On the other hand, the hierarchical wiring algorithm is one based on a divide-and-conquer method. Therefore, the hierarchical wiring is faster than the Lee's maze algorithm in processing, and since the hierarchical wiring deals with a wiring net simultaneously, there can be obtained a result independent of the processing order. There have been introduced a Burstein method (M. Burstein and R. Pelavin, "Hierarchical Wiring Routing," IEEEE Trans. CAD, Vol. CAD-2, No. 4, pp. 223-234, 1983), a Lauther method (U. P. Lauther, "Top-down hierarchical global routing For channel less gate arrays based on linear assignment," VLSI '87, C. H. Sequin (edi for) Elsevier Science Publishers B. V. (Norhi-Holland), IFIP, pp. 141-151, 1988) and a Marek-Sadowska method (M. Marek-Sadowska, "Route planner for custom chip design," Proc. of IEEE ICCAD-86, pp. 246-249, 1986) which can be classified into the above hierarchical wiring.
When a further larger scale circuit is embedded in the single chip in the near future, data handled by a wiring program will be further increased. Consequently, a processing time therefor is further increased, thus a further sped-up wiring algorithm is required so that a result can be obtained within a practical period of time. Considering the above background in the field of CAD, it can be safely said that the hierarchical wiring algorithm is one of the most important algorithms for the automatic wiring faced with a future situation where there will be a huge amount of data for wiring the LSI.
However, since the hierarchical algorithm can not consider information concerning a local wiring congestion, there is the possibility that wiring becomes impossible at a final level. In particular, if there exists an inhibited area occupying a large area in the wiring region, it is very difficult to perform a process taking the inhibited area into consideration at an upper level of the hierarchical algorithm in the course of carrying out a top-down hierarchical process.
However, in recent years, sea-of-gates (SOG) architectures as a gate-array design style have been introduced and widely used. The SOG can achieve a very high density and can contain macro-blocks (mega-cells) such as a ROM (read only memory) and RAM (random access memory) therein. There is an ever increasing demand for realizing a hierarchical algorithm capable of coping with the situation where the macro-blocks are mixed in the LSI circuit. FIG. 1 shows a nucleus of SOG, where basic cells (BC) are regularly spread all over a chip D in a two dimensional plane. A logic circuit is constituted by combining a plurality of the basic cells and wiring internally thereon.
In general, the automatic wiring is carried out in two stages in view of the processing time. One stage is a global wiring and another is a detailed wiring. The global wiring determines a rough route for a net. The route is determined on coarse grids (global grids) indicated with G13 through G33 (FIG. 2B) containing a plurality of detailed grids (wiring grids) indicated with broken lines (FIG. 2A). In the detailed wiring following the global wiring, the wiring is performed over a part of the chip considering a set-up of a via and a constraint of design rules, in order to decrease a size of problem to be handled. In the detailed wiring, the above process is repeated until wiring for the whole region is completed.
In the global wiring, calculated is a wire capacity that shows how many wiring tracks exist where a net can pass against each boundary side of the coarse grid considering an obstacle. The wire capacity is calculated for G.sub.ij (i, j=1, 2, 3) enclosed by the the global grids (FIG. 2B). A global wiring problem is to determine global routing for whole nets without exceeding the wire capacity value of each boundary side.
With reference to FIG. 3A through FIG. 9, examples of the conventional algorithms will be described in detail.
Selected and explained below is the Lauther's algorithm where division into two portions over the wiring region is repeated as an example of the hierarchical algorithms.
FIGS. 3A-3E show how the region is divided hierarchically. In FIG. 3A, DO,1 shows the wiring region such as a chip. The region DO,1 is cut by a cut-line in either a horizontal or vertical direction in a process carried out in the first layer as shown in FIG. 3B, and a passing position is determined for a net which crosses the cut-line. The net is a collection of wire requests between terminals of the same electric potential. Then, the following shall be taken into account: assignment shall not be made beyond the wire capacity of each global grid boundary on the cut-line and a wire length of net shall be minimum.
The above problem can be efficiently solved as a linear assignment problem using a network floor algorithm. A cut-net assignment for the cut-line is performed for the each partial region and such procedure is repeated until a minimum size is obtained as shown in FIG. 3E. Here, the cut-net indicates the net (routing) crossing the cut-line, namely, the net given for a certain cut-line.
FIGS. 4A-4D illustrate how the wire routing is determined. In the same figure, T indicates a terminal and CP indicates a pseudo-terminal crossing the cut-line L. In the order of FIG. 4A through 4D, the routing is determined along a top-down hierarchical router's progression.
Next, there are described drawbacks for the conventional hierarchical global wiring as follows.
Now, suppose that there are two layers which can be used for wiring. Besides cells for simple logic circuits such as NAND and NOR, in the SOG there may exist the macro-blocks with a large size such as a ROM and RAM. Generally, the first and second layers are utilized for designing to constitute functions of the macro-blocks. Therefore, a general net can not pass through the region occupied by the macro-blocks.
In the conventional hierarchical wiring process, there is taken no special consideration for dealing with the macro-blocks. Thus, in the course of processing the hierarchical wiring the wiring may have passed through the prohibited area where the macro-blocks are embedded. Examples illustrating that the wiring passes through the macro-block regions are shown in FIG. 5 and FIG. 6.
In both FIG. 5 and FIG. 6, M and M1 through M3 show macro-blocks and L1 through L5 show the cut-lines which are inserted for dividing the chip. In the same figures, all cut-lines for completing whole routes are not shown. T, A and B show terminals where the route shall be determined between the terminals having the same character.
With reference to FIG. 5, the cut-lines are inserted in the order of L1 and L2, and the position of the pseudo-terminal CP is determined. Then, the cut-line L3 is inserted. Thus, there remains a connecting request between CP and T within the region enclosed by cut-lines (L1, L2, L3) and a circumference of the chip. In order to realize the connecting request between CP and T, the wiring therefor will pass through the macro-block in the course of hierarchical process. As mentioned above, even though there is not available a region to pass through, the wiring passes through the region, thus resulting in contradiction. FIG. 6 shows a complicated example where there occurs the same kind of problem when there are plurality of macro-blocks and multiple terminal nets in the wiring region.
The above problem occurs because in the course of dividing the region by a hierarchical process the cut-lines are inserted without considering the existence of the macro-blocks. There are available the conventional methods for inserting the cut-lines as shown in FIG. 7 and FIG. 8.
FIG. 7 shows a flow chart where the number of cut-nets is D and the wire capacity on the cut-line is S, and the cut-line is chosen on the current region in such a manner that a difference (D-S) is the largest. Here, the wire capacity is the maximum number of wires that may cross a predetermined region.
In a method shown in FIG. 8, after a direction for the cut-line is determined in a manner that the region is as close to a square as possible, the cut-lines having the least number of cut-lines are preferentially chosen when the difference (D-S) is less than a threshold (THRHD). This method is based on a principle that an error value is kept minimal when making a decision at a higher level of the hierarchical processing and the both divided regions are made independent as much as possible.
In the above methods, the existence of the macro-blocks is not taken into consideration. Thus, the cut-lines as shown in FIG. 5 and FIG. 6 may occur.
Moreover, when the cut-lines are inserted ignoring the existence of the macro-blocks, there occurs wiring congestion around a portion marked with dotted line P near the region enclosed by the cut-line L and the macro-block M as shown in FIG. 9, thus causing a problem where the number of an assigned net exceeds the wire capacity at a lower level of the hierarchical processing.
Moreover, in the above two methods concerning division of the region as shown in FIG. 7 and FIG. 8, a plurality of evaluation terms are not considered simultaneously. For instance, in the method shown in FIG. 7, decision is made by a single evaluation term alone of the difference between the number of cut nets and the wire capacity. Therefore, if there are a plurality of cut-lines having a same evaluation value with this evaluation term, the position is determined at random. In this connection, there may be a case where a cut-line is chosen so that there are provided two regions each of which has a totally different area and aspect ratio to the other. In such an uneven division, an advantage of the high speed divide-and-conquer in the hierarchical algorithm can not be fully exhibited.
In the method shown in FIG. 8 as well, since there are a plurality of candidates for the cut-line and the number of cuts is in general likely to be less around the region when the cells are automatically arranged, there is a strong possibility where the cut-line near the region is chosen. As a result, balance of the two divided regions is not desirable in terms of the aspect ratio, so that there may be generated a rectangular region where one side is far too long against other shorter side and an undesirable redundant routing may result.
In the conventional automatic wiring method of the hierarchical algorithm as described above, when there are prohibited areas such as macro-blocks covering relatively large portions of the whole chip area, the wiring may cross the prohibited area in the course of hierarchical processing and the portion in the vicinity of the prohibited area often becomes congested, resulting in an undesirable routing generated.
Moreover, the position to divide the chip is determined only by a single evaluation term, so that other important evaluation terms for dividing the chip are not considered thus an overall optimum division can not be performed in the conventional hierarchical wiring method.